package com.cn.codebrush.数组.回溯;

import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

/**
 * @Author Boolean
 * @Date 2022/7/13 11:16
 * @Version 1.0
 */
public class No491递增子序列 {
    public static void main(String[] args) {
        int[] nums = {4,7,7};
        System.out.println(findSubsequences(nums));
        //System.out.println(grayCode(4));  // 16
        //System.out.println(1^3);

    }


    static List<List<Integer>> reslist = new ArrayList<>();
    public static List<List<Integer>> findSubsequences(int[] nums) {
        findSubsequencesHelper(nums,0,new ArrayList<Integer>());
        return reslist;
    }
    public static void findSubsequencesHelper(int[] nums,int start,List<Integer> list) {
        if(list.size()>1 && start <= nums.length){
            reslist.add(new ArrayList<Integer>(list));
        }
        if(start == nums.length){
            return;
        }

        //其实用数组来做哈希，效率就高了很多。
        //注意题目中说了，数值范围[-100,100]，所以完全可以用数组来做哈希。
        int[] used = new int[201];
        for(int i=start;i<nums.length;i++){
            if (used[nums[i] + 100] == 1) continue;
            used[nums[i] + 100] = 1;
            if(list.size() == 0){
                list.add(nums[i]);
            }else {
                if(i>0 && nums[i] >= list.get(list.size()-1)){
                    list.add(nums[i]);
                }else {
                    continue;
                }
            }
            findSubsequencesHelper(nums,i+1,list);
            list.remove(list.size()-1);
        }

    }


    /**
     * set 去重
     */
    Set reslist1 = new HashSet();
    public  List<List<Integer>> findSubsequences1(int[] nums) {
        findSubsequencesHelper1(nums,0,new ArrayList<Integer>());
        return new ArrayList<>(reslist);
    }
    public  void findSubsequencesHelper1(int[] nums,int start,List<Integer> list) {
        if(list.size()>1 && start <= nums.length){
            reslist.add(new ArrayList<Integer>(list));
        }
        if(start == nums.length){
            return;
        }

        for(int i=start;i<nums.length;i++){
            if(list.size() == 0){
                list.add(nums[i]);
            }else {
                if(i>0 && nums[i] >= list.get(list.size()-1)){
                    list.add(nums[i]);
                }else {
                    continue;
                }
            }
            findSubsequencesHelper1(nums,i+1,list);
            list.remove(list.size()-1);

        }

    }
}
